package nl.utwente.ewi.hmi.multitouch.analysis.segmentation;

import java.awt.Dimension;
import java.awt.geom.AffineTransform;
import java.awt.geom.FlatteningPathIterator;
import java.awt.geom.Path2D;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

import javolution.util.FastSet;

import nl.utwente.ewi.hmi.multitouch.Tangible;
import nl.utwente.ewi.hmi.multitouch.TouchDeviceInfo;
import nl.utwente.ewi.hmi.multitouch.analysis.Segment;
import nl.utwente.ewi.hmi.multitouch.io.TouchStream.Frame;
import nl.utwente.ewi.hmi.multitouch.io.TouchStream.FrameBuffer;
import nl.utwente.ewi.hmi.multitouch.io.TouchStream.TouchType;
import nl.utwente.ewi.hmi.multitouch.util.IntQueue;

public class ComponentFillSegmentation extends FrameSegmentation {

	// For each pixel in a frame, know which segment is associated with it
	private final int[] pixelToSegment;

	// For each segment, store the pixels associated with it
	private final int[] segments;

	// Job queue of pixels to examine for the pixel conquer algorithm
	private final IntQueue queue;

	private final Set<Segment> segmentSet;
	
	private Dimension size = null;
	
	public ComponentFillSegmentation(TouchDeviceInfo touchDeviceInfo) {
		super(touchDeviceInfo);

		this.size = touchDeviceInfo.getSize();

		pixelToSegment = new int[size.width * size.height];
		segments = new int[size.width * size.height];
		
		this.queue = new IntQueue(128);
		segmentSet = new HashSet<Segment>();

	}

	public Set<Segment> segment(FrameBuffer buffer) {
		final long time = System.currentTimeMillis();
		segmentSet.clear();

		// Find all segments
		for (int f = 0; f < buffer.getFrameCount(); f++) {

			// Prepare clean frame
			final Frame analyzeFrame = buffer.getFrame(f);

			final Tangible[] tangibleMap = analyzeFrame.getTangibleMap();
			final TouchType[] touchTypeMap = analyzeFrame.getTouchTypeMap();

			int minSize = 1;
//			int maxSize = 65535;

			
			// Discard any old registered segments
			Arrays.fill(pixelToSegment, 0);
			Arrays.fill(segments, 0);

			// Empty the queue's to do list
			queue.clear();

			// Mark the first segment as id 1 (by starting at id 0)
			int segmentId = 0;

			// Reset the segment offset
			int segmentOffset = 0;

			// Fill all segments left to right, top to bottom
			for (int i = 0; i < pixelToSegment.length; i++) {
				// Don't conquer already conquered segments
				if (pixelToSegment[i] > 0) {
					continue;
				}

				Tangible sample = tangibleMap[i];

				// Whenever a "negative" sample is detected, skip it
				if (sample == null || touchTypeMap[i] == TouchType.NEGATIVE
						|| touchTypeMap[i] == TouchType.NEVER) {
					continue;
				}

				boolean isAmbiguous = touchTypeMap[i] == TouchType.UNCERTAIN;
				
				segmentId++;
				int segmentSize = 0;

				// Sum of x/y
				long sx = 0;
				long sy = 0;

				int minx = Integer.MAX_VALUE;
				int maxx = 0;
				int miny = Integer.MAX_VALUE;
				int maxy = 0;

				pixelToSegment[i] = segmentId;

				segments[segmentOffset] = i;
				segmentOffset++;
				segmentSize = 1;

				// Got a new Patch te find
				queue.offer(i);

				while (!queue.isEmpty()) {
					int current = queue.poll();

					int x = current % size.width;
					int y = current / size.width;

					minx = Math.min(x, minx);
					miny = Math.min(y, miny);
					maxx = Math.max(x, maxx);
					maxy = Math.max(y, maxy);

					sx += x;
					sy += y;

					for (int dy = -1; dy <= 1; dy++) {
						for (int dx = -1; dx <= 1; dx++) {
							// Only consider directly attached pixels
							if (Math.abs(dx) == Math.abs(dy)) {
								continue;
							}

							// candidate y & candidate x
							int cy = y + dy;
							int cx = x + dx;

							// Watch out for the image edge
							if (cy < 0 || cy >= size.height || cx < 0
									|| cx >= size.width) {
								continue;
							}

							int candidate = cy * size.width + cx;

							// Don't reconquer candidates
							if (pixelToSegment[candidate] > 0) {
								continue;
							}

							// Consider the other area an edge if it is not
							// of the same tangible object, or when there is
							// no touch at the area
							boolean adjacentEdge = (tangibleMap[candidate] != sample)
									|| (touchTypeMap[candidate] == TouchType.NEGATIVE)
									|| (touchTypeMap[candidate] == TouchType.NEVER);

							if (adjacentEdge) {
								continue;
							}
							
							isAmbiguous |= touchTypeMap[candidate] == TouchType.UNCERTAIN;

							// register the pixel to the patch
							pixelToSegment[candidate] = segmentId;
							// grow patch
							segments[segmentOffset] = candidate;

							segmentOffset++;

							queue.offer(candidate);
							segmentSize++;
						}
					}
				}

				// patch size depends on image resolution
				if (segmentSize < minSize /*|| segmentSize > maxSize*/) {
					continue;
				}

				// Calculate origin

				int pcoffset = 0;


				Segment p = new ComponentFilledSegment(sample, segmentId, segmentOffset
						- segmentSize, segmentSize, pcoffset,new Rectangle2D.Float(
								minx, miny, maxx - minx, maxy - miny),
						new Point2D.Float((float) (sx / segmentSize),
								(float) (sy / segmentSize)), time, isAmbiguous);
				
				segmentSet.add(p);
			}
		}
		
		return segmentSet;
	}


	/**
	 * A Segment represent a connected set of pixels within a frame where
	 * each pixel is of the same Tangible type.
	 * 
	 * @author Michiel Hakvoort
	 */
	private class ComponentFilledSegment implements Segment {
//		SegmentBasedTouch touch = null;

		final int id;
		final int offset;
		final int length;
		final Rectangle2D boundingBox;
		final Point2D origin;
		final int edgePoints;
		final Tangible tangible;
		final long time;

		final boolean isAmbiguous;
		
		final Path2D perimeter;

		private ComponentFilledSegment(Tangible tangible, int id, int offset, int length, int edgePoints, Rectangle2D boundaries, Point2D origin, long time, boolean isAmbiguous) {
			this.tangible = tangible;
			this.id = id;
			this.offset = offset;
			this.length = length;
			this.edgePoints = edgePoints;
			this.boundingBox = boundaries;
			this.origin = origin;
			this.time = time;
			this.perimeter = new Path2D.Float();
			this.isAmbiguous = false;

			this.createPerimeter();
		}

		@Override
		public long getTime() {
			return this.time;
		}
		
		/**
		 * Get the origin of the Segment
		 * 
		 * @return
		 */
		public Point2D getOrigin() {
			return this.origin;
		}

		/**
		 * Get the bounding box of the Segment
		 * 
		 * @return
		 */
		public Rectangle2D getBounds() {
			return this.boundingBox;
		}

		/**
		 * Get the Tangible type of the Segment
		 * 
		 * @return
		 */
		public Tangible getTangible() {
			return this.tangible;
		}

		@Override
		public float getMass() {
			return this.length;
		}

		@Override
		public Path2D getPerimeter() {
			return this.perimeter;
		}


		/**
		 * Create the perimeter of the Segment by scanning the side using
		 * the Marching Squares algorithm, in the meanwhile vertex reduction
		 * is used to minify the load for the simplification of the
		 * perimeter, performed by the Ramer-Douglas-Peucker algorithm.
		 */
		private void createPerimeter() {
			Path2D perimeter = new Path2D.Float();

			int xStart = (segments[offset] % size.width) - 1;
			int yStart = (segments[offset] / size.width) - 1;

			int x = xStart;
			int y = yStart;

			int previousX = x;
			int previousY = y;

			perimeter.moveTo(x, y);

			do {
				int square = (occupied(x, y) << 3)
						| (occupied(x + 1, y) << 2)
						| (occupied(x, y + 1) << 1)
						| occupied(x + 1, y + 1);

				switch (square) {
				// 00      00         01         01
				// 10      11         10         11         Travel to the east
				case 0x02: case 0x03: case 0x06: case 0x07: x--; break;
				// 01      11         11
				// 00      00         10                    Travel to the west
				case 0x04: case 0x0C: case 0x0E:            x++; break;
				// 01      00         11
				// 01      01         01                    Travel to the south
				case 0x05: case 0x01: case 0x0D:            y++; break;
				// 10      10         10         10
				// 00      01         10         11         Travel to the north
				case 0x08: case 0x09: case 0x0A: case 0x0B: y--; break;
				// 11 00 
				// 11 00 Invalid state
				default:
				}

				// Apply simple vertex reduction
				if (Math.sqrt(Math.pow(previousX - x, 2)
						+ Math.pow(previousY - y, 2)) >= 2) {
					perimeter.lineTo(x, y);
					previousX = x;
					previousY = y;
				}
			} while (x != xStart || y != yStart);

			perimeter.lineTo(x, y);
			
			this.perimeter.append(new FlatteningPathIterator(perimeter.getPathIterator(ComponentFillSegmentation.this.touchDeviceInfo.getTransform()), 1d, 32), false);
		}

		int occupied(int x, int y) {
			if (x < 0 || x >= size.width || y < 0 || y >= size.height)
				return 0;
			return (pixelToSegment[y * size.width + x] == this.id) ? 1 : 0;
		}

		@Override
		public int compareTo(Segment o) {
			return (int)(this.getTime() - o.getTime());
		}

		@Override
		public boolean isAmbiguous() {
			// TODO Auto-generated method stub
			return false;
		}

	}
}
